﻿#pragma once
# include <iostream>
# include <assert.h>
# include <vector>
using namespace std;


template<class K ,class V >
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;    //在平衡二叉树的基础上加了一个patent指针
	int _bf;                       //平衡因子  右子树高度-左子树高度

	AVLTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
	    , _right(nullptr)
	    , _parent(nullptr)
		,_bf(0)
	{
	}
};
template<class K,class V>
class AVLTree
{
public:
	typedef AVLTreeNode<K,V> Node;
	void RotateR(Node* parent)
	{
		Node* subl=parent->_left;          
		Node* sublR = subl->_right;
		parent->_left = sublR;   //先将subl的右给了parent的左 
		subl->_right = parent;   //然后parent变为subl的右

		//还需要处理parent和subl的平衡因子和parent指针的指向问题
		parent->_bf = subl->_bf = 0;

		if (sublR)
		{
			sublR->_parent = parent;
		}
		Node* pparent = parent->_parent;       //在改变parent的parent指针之前先存一下
		parent->_parent = subl;  //还需要改变parent的parent指针
		 //处理pparent的指向问题
		if (pparent)              //pparent不为空就让pparent指向subl
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subl;
			}
			else
			{
				pparent->_right = subl;
			}
		}
		else   //如果pparent为空 说明parent就是根节点 那么直接更新根节点为parent
		{
			_root = subl;
		}
		subl->_parent = pparent;
	}

	void RotateL(Node* parent)
	{
		Node* subl = parent->_right;
		Node* sublL = subl->_left;
		parent->_right = sublL;
		subl->_left = parent;

		if (sublL)
		{
			sublL->_parent = parent;
		}
		parent->_bf = subl->_bf = 0;
		
		Node* pparent = parent->_parent;
		parent->_parent = subl;

		if (pparent)
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subl;
			}
			else
				pparent->_right = subl;
		}
		else
		{
			_root = subl;
		}
		subl->_parent = pparent;

	}
	void RotateLR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublR = subl->_right;
		int cou = sublR->_bf;   //先存一下该节点的平衡因子 如果是1那就是右树高度增加 最终parent平衡因子为0subl为-1
		                                               //如果是-1就是左树高度增加 最终parent平衡因子为subl为0
		RotateL(subl);         //先对subl进行左单旋  再对parent进行右单旋
		RotateR(parent);
		if (cou==1)          //往sublR的右插
		{
			parent->_bf = 0;
			sublR->_bf = 0;       //其实这两行不用先 在经过上面单旋双旋之后 他们平衡因子都为0了
			subl->_bf = -1;
		}
		else if (cou == -1)     //往sublR的左插
		{
			sublR->_bf = 0;
			subl->_bf = 0;
			parent->_bf = 1;
		}
		else if (cou == 0)               //p                   //刚开始h为0的特殊情况
		{                        // subl  
			sublR->_bf = 0;      //       sublR新插入的     
			subl->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	void RotateRL(Node* parent)
	{
		Node* subl= parent->_right;
		Node* sublL = subl->_left;
		int con=sublL->_bf;
		RotateR(subl);
		RotateL(parent);
		if (con == 1)
		{
			subl->_bf = 0;
			sublL->_bf = 0;
			parent->_bf = -1;
		}
		else if (con == -1)
		{
			subl->_bf = 1;
			sublL->_bf = 0;
			parent->_bf = 0;
		}
		else if (con == 0)            
		 {
			 subl->_bf = 0;
			 sublL->_bf = 0;
			 parent->_bf = 0;
		 }
		else
		{
			assert(false);
		}
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
				if (cur->_kv.first < key)
				{
						cur = cur->_right;
				}
				else if (cur->_kv.first > key)
				{
						cur = cur->_left;
				}
				else
				{
						return cur;
				}
		}
		return nullptr;
	}

	bool insert(const pair<K,V>& kv)
	{
		if (_root == nullptr)  //对空树的处理
			_root = new Node(kv);

		Node* cur = _root;
		Node* curparent = cur;
		while (cur != nullptr)              //直到为空了  就是要插入的位置
		{
			if (kv.first > cur->_kv.first)             //要插入的数大于根的值就往右
			{
				curparent = cur;          //cur里面存的是cur的上一个位置 cur改变之前先把它的位置存到curparent中
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)       //小于根的值就往左
			{
				curparent = cur;
				cur = cur->_left;
			}
			else
				return false;        //不支持插入重复的元素 插入失败 返回false
		}
		
		//如果正常出了循环 那么此时cur的位置就是新插入节点的位置 那么此时为新节点开空间 然后让它的父节点指向它
		cur= new Node(kv);
		if (curparent->_kv.first < kv.first)
			curparent->_right = cur;          //此时还需要判断 cur位置的节点是父节点的右孩子还是左孩子
		else
			curparent->_left = cur; 

		cur->_parent = curparent;           //处理节点的parent指针

		
		//根据curparent平衡因子改变后的结果做处理
		while (curparent)          //刚开始的curparent就是新插入节点的parent 
		{
			//对平衡因子做处理
			if (cur == curparent->_left)
				curparent->_bf--;
			else
				curparent->_bf++;

			//根据父节点平衡因子的情况做不同处理
			if (curparent->_bf == 0)      //从1或者-1到0的情况
				return true;
			else if (curparent->_bf == 1 || curparent->_bf == -1)  //从0到1或者到-1的情况  继续向上处理
			{
				cur = curparent;
				curparent = curparent->_parent;
			}
			else if (curparent->_bf == 2 || curparent->_bf == -2)    //从1到2或者从-1到-2的情况 需要旋转处理
			{
				//旋转处理
				if (curparent->_bf == -2 && cur->_bf == -1)  //右单旋
					RotateR(curparent);
				else if (curparent->_bf == 2 && cur->_bf == 1) //左单旋
					RotateL(curparent);
				else if (curparent->_bf == -2 && cur->_bf == 1)   //左右双旋
					RotateLR(curparent);
				else if (curparent->_bf == 2 && cur->_bf == -1) //右左双旋
					RotateRL(curparent);

				break;
			}
			else     //其实正常情况的话这种情况就不会发生 但是可能出现错误 这样就会更容易发现
				assert(false);
		}
		return true;   //插入成功 返回true
	}
	int Height()
	{
		return _Height(_root);
	}
	int size()
	{
		return _size(_root);
	}
	int _size(Node* root)
	{
		if (root == nullptr)
			return 0;
		return _size(root->_left) + _size(root->_right)+1;
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
			if (nullptr == root)
				return true;
		// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差

			int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		
			// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
			if (abs(diff) >= 2)
			{
				cout << root->_kv.first << "高度错误" << endl;
					return false;
			}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
				return false;
		}
		// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
			return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
	void Midbl()    //中序遍历的形参类型需要为节点  但是我们创建的对象是BStree类型 且里面的root根节点为私有
	{                         //所以 我们可以提供一个返回根节点的函数 或者像之前实现归并非递归那样做一层封装
		Midbl1(_root);
	}
		
	void Midbl1(Node* root)   //中序遍历  先左再中再右 对搜索二叉树来说也就是从小到大的顺序打印
	{
		if (root == nullptr)
		{
			return;
		}
		Midbl1(root->_left);
		cout << root->_kv.first << " ";
		Midbl1(root->_right);
	}
	
private:
	Node* _root=nullptr;
};
